package VNF_DelayLBA_large;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.net2plan.interfaces.networkDesign.Demand;
import com.net2plan.interfaces.networkDesign.Link;
import com.net2plan.interfaces.networkDesign.NetPlan;
import com.net2plan.interfaces.networkDesign.NetworkLayer;
import com.net2plan.interfaces.networkDesign.Node;
import com.net2plan.libraries.GraphUtils;

public class MyUtil {
	
	public static int numberofallslot = 300 ;
	public static int numberOfKShortestPath = 3;
	public static int numberOfKLinkmapping = 3;
	public static double BPSKmaxlength = 4000.0;
	public static double QPSKmaxlength = 2000.0;
	public static double QAM_8maxlength = 1000.0;
	public static double QAM_16maxlength = 500.0;
	
	/**
	 * 移除这个网络中的所有分层
	 * @param netplan 要操作的网络拓扑
	 * @return 默认层
	 */
	public static NetPlan removeLayers(NetPlan netplan){
		List<Long> names = new ArrayList<Long>();
		int numberofnetworklayers = netplan.getNumberOfLayers();
		for (int i=1;i<numberofnetworklayers;i++){
			Long name = netplan.getNetworkLayer(i).getId();
			names.add(name);
		}
		for (Long name : names){
			netplan.removeNetworkLayer(netplan.getNetworkLayerFromId(name));
			netplan = netplan.copy();
		}
		return netplan;
	}
	
	public static NetPlan substrateNetplanAttribute(NetPlan netplan){
		Tool_Util tool = new Tool_Util();
		List<Link> links = new ArrayList<Link>();
		links = netplan.getLinks();
		String capacityofslots = tool.setAttributeOfSituationOfSlots(numberofallslot);
		for (Link link : links){
			link.setAttribute("linkstatus", capacityofslots);
			link.setCapacity(numberofallslot);
		}
		return netplan;
	}
	
	public static NetPlan removeAllLayerDemand(NetPlan netplan){
		for (NetworkLayer networklayer : netplan.getNetworkLayers()){
			netplan.removeAllDemands(networklayer);
		} 
		return netplan;
	}
	
	/**
	 * 节点映射过程
	 * @param subNetPlan 物理网络
	 * @param request 请求
	 */
	public static NodeMappingReturn nodeMapping(NetPlan subNetPlan,NetPlan request) {
		NodeMappingReturn nodeMappingReturn = new NodeMappingReturn();
		Tool_Util tool = new Tool_Util();
		boolean sign = true;
		int sourceNodeIndex,destinationNodeIndex;
		//存放节点之间的对应关系
		Map<Node,Node> nodePair = new HashMap<Node, Node>();
		Map<Node,Node> vnfnodepair = new HashMap<Node,Node>();
		//存放请求中所需的VNF序列
		List<String> VNFSeq = new ArrayList<String>();
		//请求中的所有节点
		List<Node> VNFnetplannodes = request.getNodes();
		//选择节点的依据
		Map<Node,Integer> VNFOnDC = new HashMap<Node,Integer>();
		//请求的所有节点数量
		int numberOfRequestNodes = request.getNumberOfNodes();
		//物理网络中的节点数量
		int numberOfSubNodes = subNetPlan.getNumberOfNodes();
		//物理网络中的所有节点
		List<Node> subNodeList = subNetPlan.getNodes();
		//请求中的link集合
		List<Link> requestLinkList = request.getLinks();
		List<Node> vnfnodes = new ArrayList<Node>();
		for(int i =1;i<=numberOfRequestNodes-2;i++) {
			vnfnodes.add(VNFnetplannodes.get(i));
		}
		
		List<Integer> lengthofCS = new ArrayList<Integer>();
		List<List<Map.Entry<Node, Node>>> tempnodepairlist = new ArrayList<List<Map.Entry<Node,Node>>>();

				
		for(int i=1;i<numberOfRequestNodes-1;i++) {
			VNFSeq.add(request.getNode(i).getAttribute("VNF"));
		}
		System.out.print("所需VNF ");
		for(String s : VNFSeq) {
			System.out.print(s+" ");
		}
		System.out.println();
		//先分配好源节点和目的节点的位置
		Node sourceNode = request.getNode(0);
		Node destinationNode = request.getNode(numberOfRequestNodes-1);
		sourceNodeIndex = (int)(Math.random()*numberOfSubNodes);
		System.out.println("源节点"+sourceNodeIndex);
		while(true) {
			destinationNodeIndex = (int)(Math.random()*numberOfSubNodes);
			if(destinationNodeIndex!=sourceNodeIndex) {
				break;
			}
		}
		System.out.println("目的节点"+destinationNodeIndex);
		nodePair.put(sourceNode, subNetPlan.getNode(sourceNodeIndex));
		nodePair.put(destinationNode, subNetPlan.getNode(destinationNodeIndex));
		sourceNode.setAttribute("MappedNode", String.valueOf(sourceNodeIndex));
		destinationNode.setAttribute("MappedNode", String.valueOf(destinationNodeIndex));
		sourceNode.setAttribute("deployed", "1");
		destinationNode.setAttribute("deployed", "1");
		
		//获取源目的节点之间的多条最短路径
		Map<Link,Double> linkCostMap = new HashMap<Link,Double>();
		for(Link link:subNetPlan.getLinks()) {
			linkCostMap.put(link, link.getLengthInKm());
		}
		List<List<Link>> kShortestPathList = GraphUtils.getKLooplessShortestPaths(subNetPlan.getNodes(), subNetPlan.getLinks(), subNetPlan.getNode(sourceNodeIndex), subNetPlan.getNode(destinationNodeIndex), linkCostMap, numberOfKShortestPath, Double.MAX_VALUE, Integer.MAX_VALUE , Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
		//对所有最短路径上的所有数据中心节点进行遍历
		for(List<Link> shortestpath:kShortestPathList) {
			
			int flag = 0;
			Map<Node,Node> tempvnfnodepair = new HashMap<Node,Node>();
			List<Map.Entry<Node, Node>> tempnodepair = new ArrayList<Map.Entry<Node,Node>>();
			List<Node> removenodelist = new ArrayList<Node>();
			List<Node> tempnodelist = new ArrayList<Node>();
			tempnodelist.add(shortestpath.get(0).getOriginNode());
			for(Link templink : shortestpath) {
				tempnodelist.add(templink.getDestinationNode());
			}
			
			 for(int i = 0;i<numberOfRequestNodes-2;i++) {
				 for(Node removenode:removenodelist) {
			    		if(tempnodelist.contains(removenode)) {
			    			tempnodelist.remove(removenode);
			    		}
			    	}
				 int vnftype = Integer.valueOf(VNFSeq.get(i)).intValue();
				 int numberoftempnode = tempnodelist.size();
				 for(int j = 0;j<numberoftempnode;j++) {
					 List<Integer> subnodevnflist = new ArrayList<Integer>();
					 int[] subnodevnf = tool.stringToIntArray(tempnodelist.get(j).getAttribute("VNF"));
					 for(int a : subnodevnf) {
			    			subnodevnflist.add(a);
			    	}
					 if(subnodevnflist.contains(vnftype)){
						 tempvnfnodepair.put(request.getNode(i+1), tempnodelist.get(j));
						 tempnodepair.addAll(tempvnfnodepair.entrySet());
						 flag++;
			    		 for(int n = 0;n<j;n++) {
			    				removenodelist.add(tempnodelist.get(n));
			    		 }
			    			
			    		 break;
					 }
				 }
			 }
			 lengthofCS.add(flag);
			 tempnodepairlist.add(tempnodepair);	 
		}

		int kmax = Collections.max(lengthofCS);
		int knum = lengthofCS.indexOf(kmax);
		
		if(kmax > 0) {
			 List<Link> selectedpath = kShortestPathList.get(knum);
			 List<Node> subnodeonpath = new ArrayList<Node>();
			 subnodeonpath.add(selectedpath.get(0).getOriginNode());
			 for(Link link:selectedpath) {
					subnodeonpath.add(link.getDestinationNode());
			 }
			 List<Map.Entry<Node, Node>> tempnodepaironpath =  tempnodepairlist.get(knum);
			 for(Map.Entry<Node, Node> e : tempnodepaironpath) {
				 if(subNodeList.indexOf(e.getValue())<0) {
					 sign=false;
					 nodeMappingReturn.setSign(sign);
					 return nodeMappingReturn;
				 }
				 vnfnodepair.put(e.getKey(), e.getValue()); 
				 e.getKey().setAttribute("deployed", "1");
				 e.getKey().setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(e.getValue())));
				 Node selecteddc = e.getValue();
				 String vnftype = e.getKey().getAttribute("VNF");
				 int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
				 before++;
				 selecteddc.setAttribute(vnftype, String.valueOf(before));
			 }
			 
			 List<Node> RV = new ArrayList<Node>();
			 for(int i = 1;i<numberOfRequestNodes-1;i++) {
				 if("0".equals(request.getNode(i).getAttribute("deployed"))) {
					 RV.add(request.getNode(i));
				 }
			 }
			 
			 for(Node undeployednode : RV) {
				 int indexinrequestofthisnode=VNFnetplannodes.indexOf(undeployednode);
				 int indexinrequestofbefore = indexinrequestofthisnode-1;
				 int indexinrequestofbehind = 0;
				 for(int i=indexinrequestofthisnode+1;i<numberOfRequestNodes;i++) {
					 if(VNFnetplannodes.get(i).getAttribute("deployed").equals("1")) {
						 indexinrequestofbehind=i;
						 break;
					 }
				 }
				 int indexsubnodebefore = Integer.valueOf(VNFnetplannodes.get(indexinrequestofbefore).getAttribute("MappedNode")).intValue();
				 Node subnodebefore = subNodeList.get(indexsubnodebefore);
				 int indexsubnodebehind = Integer.valueOf(VNFnetplannodes.get(indexinrequestofbehind).getAttribute("MappedNode")).intValue();
				 Node subnodebehind = subNodeList.get(indexsubnodebehind);
				 
				 if(subnodebefore.equals(subnodebehind)) {
					 Node selecteddc = subnodebefore;
					 if(subNodeList.indexOf(selecteddc)<0) {
						 sign=false;
						 nodeMappingReturn.setSign(sign);
						 return nodeMappingReturn;
					 }
					 vnfnodepair.put(undeployednode, selecteddc);
					 undeployednode.setAttribute("deployed", "1");
				     undeployednode.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
				     StringBuilder str = new StringBuilder();
					 str.append(selecteddc.getAttribute("VNF"));
				     String vnftype = undeployednode.getAttribute("VNF");
				     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
					 if(before==0) {
							str.append(vnftype);
					 }
					 before++;
					 selecteddc.setAttribute(vnftype, String.valueOf(before));
					 selecteddc.setAttribute("VNF", str.toString());
				 } else {
					 int firstlinkindex=0;
					 int lastlinkindex=0;
					 for(int i =0;i<selectedpath.size();i++) {
						 if(selectedpath.get(i).getOriginNode().equals(subnodebefore)) {
							 firstlinkindex=i;
							 break;
						 }
					 }
					 for(int i =0;i<selectedpath.size();i++) {
						 if(selectedpath.get(i).getDestinationNode().equals(subnodebehind)) {
							 lastlinkindex=i;
							 break;
						 }
					 }
					 double lengthbetweentwonodes = 0.0;
					 for(int i =firstlinkindex;i<=lastlinkindex;i++) {
						 lengthbetweentwonodes=lengthbetweentwonodes+selectedpath.get(i).getLengthInKm();
					 }
					 int numberofdcneeded=(int)Math.ceil(lengthbetweentwonodes/BPSKmaxlength)-1;
					 
					 List<Node> dcbetweentwonodes = new ArrayList<Node>();
					 
					 int numberofdcbetweentwonodes = 0;
		
					 for(int i =firstlinkindex+1;i<=lastlinkindex;i++) {
						 if(subnodeonpath.get(i).getAttribute("DataCenter").equals("1")) {
							 dcbetweentwonodes.add(subnodeonpath.get(i));
							 numberofdcbetweentwonodes++;
						 }
					 }
					 if(numberofdcneeded==0) {
						 if(numberofdcbetweentwonodes>0) {
							 Node selecteddc = dcbetweentwonodes.get(0);
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode, selecteddc);
							 undeployednode.setAttribute("deployed", "1");
						     undeployednode.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 } else {
							 if(subnodebefore.getAttribute("DataCenter").equals("1")) {
								 Node selecteddc = subnodebefore;
								 if(subNodeList.indexOf(selecteddc)<0) {
									 sign=false;
									 nodeMappingReturn.setSign(sign);
									 return nodeMappingReturn;
								 }
								 vnfnodepair.put(undeployednode, selecteddc);
								 undeployednode.setAttribute("deployed", "1");
							     undeployednode.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
							     StringBuilder str = new StringBuilder();
								 str.append(selecteddc.getAttribute("VNF"));
							     String vnftype = undeployednode.getAttribute("VNF");
							     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
								 if(before==0) {
										str.append(vnftype);
								 }
								 before++;
								 selecteddc.setAttribute(vnftype, String.valueOf(before));
								 selecteddc.setAttribute("VNF", str.toString());
							 } else {
								 for(int i = 0;i<subnodeonpath.size();i++) {
									 if(subnodeonpath.get(i).getAttribute("DataCenter").equals("1")){
										 Node selecteddc = subnodeonpath.get(i);
										 if(subNodeList.indexOf(selecteddc)<0) {
											 sign=false;
											 nodeMappingReturn.setSign(sign);
											 return nodeMappingReturn;
										 }
										 vnfnodepair.put(undeployednode, selecteddc);
										 undeployednode.setAttribute("deployed", "1");
									     undeployednode.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
									     StringBuilder str = new StringBuilder();
										 str.append(selecteddc.getAttribute("VNF"));
									     String vnftype = undeployednode.getAttribute("VNF");
									     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
										 if(before==0) {
												str.append(vnftype);
										 }
										 before++;
										 selecteddc.setAttribute(vnftype, String.valueOf(before));
										 selecteddc.setAttribute("VNF", str.toString());
										 break;
									 }
								 }
							 }
						 }
					 } else {
						 if(numberofdcbetweentwonodes>0) {
							 Node selecteddc = dcbetweentwonodes.get(0);
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode, selecteddc);
							 undeployednode.setAttribute("deployed", "1");
						     undeployednode.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 }
					 }
					 
				 }
				
			 }
			 
		} else {
			 List<Link> temppath = new ArrayList<Link>();
			 List<Node> nodeonpath = new ArrayList<Node>();
			 //����·�ϵ���������
			 List<Node> dcnodelist = new ArrayList<Node>();
			 //Դ��Ŀ�Ľڵ�֮�����������
			 List<Node> dcnodebetweensd=new ArrayList<Node>();
			 for(int kth=0;kth<numberOfKShortestPath;kth++) {
				 temppath = kShortestPathList.get(kth);
				 nodeonpath.clear();
				 dcnodelist.clear();
				 dcnodebetweensd.clear();
				 nodeonpath.add(temppath.get(0).getOriginNode());
				 for(Link link : temppath) {
					 nodeonpath.add(link.getDestinationNode());
				 }
				 for(Node node:nodeonpath) {
					 if(node.getAttribute("DataCenter").equals("1")) {
						 dcnodelist.add(node);
					 }
				 }
				 for(int i=1;i<nodeonpath.size()-1;i++) {
					 if(nodeonpath.get(i).getAttribute("DataCenter").equals("1")) {
						 dcnodebetweensd.add(nodeonpath.get(i));
					 }
				 }
				 if(!dcnodelist.isEmpty()) {
					 break;
				 }
			 }
			 if(dcnodelist.size()==0) {
				 sign = false;
				 nodeMappingReturn.setSign(sign);
				 return nodeMappingReturn;
			 }
			 double pathlength = 0.0;
			 for(Link link:temppath) {
				 pathlength=link.getLengthInKm()+pathlength;
			 }
			 int numberofdcneeded=(int)Math.ceil(pathlength/BPSKmaxlength)-1;
			 //Դ��Ŀ�Ľڵ�֮��ʵ���ж��ٸ���������
			 int numberoddcbetweensd=dcnodebetweensd.size();
			 //������Ҫ���ٸ�VNF
			 int numberofvnfneeded = vnfnodes.size();
			 
			 int middlenum=(int)Math.ceil((numberofvnfneeded*1.0)/2.0);
			 if(numberofdcneeded==0) {
				 if(numberoddcbetweensd==0) {
					 Node selecteddc = dcnodelist.get(0);
					 for(int i=0;i<middlenum;i++) {
						 Node undeployednode_before = vnfnodes.get(i);
						 {
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode_before, selecteddc);
							 undeployednode_before.setAttribute("deployed", "1");
							 undeployednode_before.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode_before.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 }
						 if(dcnodelist.size()>1) {
							 dcnodelist.remove(selecteddc);
							 selecteddc=dcnodelist.get(dcnodelist.size()-1);
						 }
						 Node undeployednode_behind = vnfnodes.get(numberofvnfneeded-1-i);
						 {
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode_behind, selecteddc);
							 undeployednode_behind.setAttribute("deployed", "1");
							 undeployednode_behind.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode_behind.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 }
						 if(dcnodelist.size()>1) {
							 dcnodelist.remove(selecteddc);
							 selecteddc=dcnodelist.get(0);
						 }
					 }
				 } else {
					 Node selecteddc = dcnodebetweensd.get(0);
					 for(int i=0;i<middlenum;i++) {
						 Node undeployednode_before = vnfnodes.get(i);
						 {
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode_before, selecteddc);
							 undeployednode_before.setAttribute("deployed", "1");
							 undeployednode_before.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode_before.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 }
						 if(dcnodebetweensd.size()>1) {
							 dcnodebetweensd.remove(selecteddc);
							 selecteddc=dcnodebetweensd.get(dcnodebetweensd.size()-1);
						 }
						 Node undeployednode_behind = vnfnodes.get(numberofvnfneeded-1-i);
						 if(!undeployednode_behind.equals(undeployednode_before)) {
							 if(subNodeList.indexOf(selecteddc)<0) {
								 sign=false;
								 nodeMappingReturn.setSign(sign);
								 return nodeMappingReturn;
							 }
							 vnfnodepair.put(undeployednode_behind, selecteddc);
							 undeployednode_behind.setAttribute("deployed", "1");
							 undeployednode_behind.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
						     StringBuilder str = new StringBuilder();
							 str.append(selecteddc.getAttribute("VNF"));
						     String vnftype = undeployednode_behind.getAttribute("VNF");
						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
							 if(before==0) {
									str.append(vnftype);
							 }
							 before++;
							 selecteddc.setAttribute(vnftype, String.valueOf(before));
							 selecteddc.setAttribute("VNF", str.toString());
						 }
						 if(dcnodebetweensd.size()>1) {
								dcnodebetweensd.remove(selecteddc);
								 selecteddc=dcnodebetweensd.get(0);
						 }
					 }
				 }
		 } 
//				 else {
//				 if(numberoddcbetweensd>0) {
//					 Node selecteddc = dcnodebetweensd.get(0);
//					 for(int i=0;i<middlenum;i++) {
//						 Node undeployednode_before = vnfnodes.get(i);
//						 {
//							 if(subNodeList.indexOf(selecteddc)<0) {
//								 sign=false;
//								 nodeMappingReturn.setSign(sign);
//								 return nodeMappingReturn;
//							 }
//							 vnfnodepair.put(undeployednode_before, selecteddc);
//							 undeployednode_before.setAttribute("deployed", "1");
//							 undeployednode_before.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
//						     StringBuilder str = new StringBuilder();
//							 str.append(selecteddc.getAttribute("VNF"));
//						     String vnftype = undeployednode_before.getAttribute("VNF");
//						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
//							 if(before==0) {
//									str.append(vnftype);
//							 }
//							 before++;
//							 selecteddc.setAttribute(vnftype, String.valueOf(before));
//							 selecteddc.setAttribute("VNF", str.toString());
//						 }
//						 if(dcnodebetweensd.size()>1) {
//							 dcnodebetweensd.remove(selecteddc);
//							 selecteddc=dcnodebetweensd.get(dcnodebetweensd.size()-1);
//						 }
//						 Node undeployednode_behind = vnfnodes.get(numberofvnfneeded-1-i);
//						 {
//							 if(subNodeList.indexOf(selecteddc)<0) {
//								 sign=false;
//								 nodeMappingReturn.setSign(sign);
//								 return nodeMappingReturn;
//							 }
//							 vnfnodepair.put(undeployednode_behind, selecteddc);
//							 undeployednode_behind.setAttribute("deployed", "1");
//							 undeployednode_behind.setAttribute("MappedNode", String.valueOf(subNodeList.indexOf(selecteddc)));
//						     StringBuilder str = new StringBuilder();
//							 str.append(selecteddc.getAttribute("VNF"));
//						     String vnftype = undeployednode_behind.getAttribute("VNF");
//						     int before = Integer.valueOf(selecteddc.getAttribute(vnftype)).intValue();
//							 if(before==0) {
//									str.append(vnftype);
//							 }
//							 before++;
//							 selecteddc.setAttribute(vnftype, String.valueOf(before));
//							 selecteddc.setAttribute("VNF", str.toString());
//						 }
//						 if(dcnodebetweensd.size()>1) {
//								dcnodebetweensd.remove(selecteddc);
//								 selecteddc=dcnodebetweensd.get(0);
//						 }
//					 }
//				 }
//			 }	 
		}
	   for(Node vnfnode:vnfnodes) {
			nodePair.put(vnfnode, vnfnodepair.get(vnfnode)); 
	   }
	   
	   if(nodePair.size()==numberOfRequestNodes) {
		   sign = true;
	   } else {
		   sign = false;
	   }
	   for(Node node : vnfnodes) {
			 String s = node.getAttribute("MappedNode");
			 int subindex = Integer.valueOf(s).intValue();
			 if(subindex<0) {
				 sign = false;
				 break;
			 }
		}
	   if(sign) {
		   for(Link link:requestLinkList) {
				int origin = subNodeList.indexOf(nodePair.get(link.getOriginNode()));
				int destination = subNodeList.indexOf(nodePair.get(link.getDestinationNode()));
				//System.out.println("origin node "+origin+" des node "+destination+" "+link.getCapacity());
				if(origin!=destination) {
					subNetPlan.addDemand(nodePair.get(link.getOriginNode()), nodePair.get(link.getDestinationNode()), link.getCapacity(), null, subNetPlan.getNetworkLayerDefault());
				}
			}
	   }
		nodeMappingReturn.setSign(sign);
		return nodeMappingReturn;
	}
	
	
	
	
	public static LinkMappingReturn linkMapping(NetPlan subNetPlan,NetPlan request) {
		List<Node> subNodes = subNetPlan.getNodes();
		List<Link> requestLinks = request.getLinks(request.getNetworkLayerDefault());
		LinkMappingReturn linkMappingReturn = new LinkMappingReturn();
		boolean  sign = true;
		System.out.println("demand "+subNetPlan.getNumberOfDemands(subNetPlan.getNetworkLayerDefault()));
		List<Demand> demandList = subNetPlan.getDemands(subNetPlan.getNetworkLayerDefault());
		Tool_Util tool = new Tool_Util();
		for(Demand demand: demandList) {
			double capacity = demand.getOfferedTraffic();
			System.out.println(capacity);
			Node startNode = demand.getIngressNode();
			Node endNode = demand.getEgressNode();
			Map<Link,Double> linkCostMap = new HashMap<Link,Double>();
			for(Link link:subNetPlan.getLinks()) {
				linkCostMap.put(link, link.getLengthInKm());
			}
			List<List<Link>> kShortestPathList = GraphUtils.getKLooplessShortestPaths(subNetPlan.getNodes(), subNetPlan.getLinks(), startNode, endNode, linkCostMap, numberOfKLinkmapping, Double.MAX_VALUE, Integer.MAX_VALUE , Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE);
			List<List<Link>> candidatePathList = new ArrayList<List<Link>>();
			for(int i=0;i<numberOfKLinkmapping;i++) {
				List<Link> temppath = kShortestPathList.get(i);
				Double pathlength = 0.0;
				for(Link link:temppath) {
					pathlength=pathlength+link.getLengthInKm();
				}
				if(pathlength<=BPSKmaxlength) {
					candidatePathList.add(temppath);
				}
			}
			if(candidatePathList.isEmpty()) {
				removeAllLayerDemand(subNetPlan);
				sign = false;
				linkMappingReturn.setSign(sign);
				return linkMappingReturn;
			}
			List<Integer> mfsiList = new ArrayList<Integer>();
			List<Link> selectedPath = new ArrayList<Link>();
			for(int i=0;i<candidatePathList.size();i++) {
				List<Link> candidatePath = candidatePathList.get(i);
				double pathLength = 0.0;
				for(Link link :candidatePath) {
					pathLength+=link.getLengthInKm();
				}
				double modLevel = 0.0;
				int key = (int)(Math.floor(pathLength/QAM_16maxlength));
				switch(key) {
					case 1: modLevel = 4.0; break;
					case 2: modLevel = 3.0; break;
					case 3: modLevel = 2.0; break;
					case 4: modLevel = 2.0; break;
					default : modLevel = 1.0; break;
				}
				int numberofslotneeded = (int)Math.ceil(capacity/(12.5*modLevel));
				int[] pathStatus = new int[numberofallslot];
				for(Link link:candidatePath) {
					String linkStatus = link.getAttribute("linkstatus");
					int[] s1 = tool.stringToIntArray(linkStatus);
					for(int m =0;m<numberofallslot;m++) {
						if(pathStatus[m]==0&&s1[m]==0) {
							pathStatus[m]=0;
						}
						else {
							pathStatus[m]=1;
						}	
					}
				}
				int startindex = 0;
				int endindex = 0;
				int flag=0;
				int count = 0;
				for(int m=0;m<numberofallslot;m++) {
					count++;
					if(pathStatus[m]==0) {
						flag++;
					}
					else {
						flag=0;
					}
					if(flag==numberofslotneeded) {
						endindex = m;
						startindex = endindex-numberofslotneeded+1;
						break;
					}
				}
				if(count==numberofallslot&&endindex==0) {
					mfsiList.add(numberofallslot+1);
					continue;
				}
				for(int m =startindex;m<=endindex;m++) {
					pathStatus[m]=1;
				}
				int mfsi=0;
				for(int m=0;m<numberofallslot;m++) {
					if(pathStatus[m]==1) {
						mfsi=m+1;
					}
				}
				mfsiList.add(mfsi);
			}
			int kmin = Collections.min(mfsiList);
			if(kmin==numberofallslot+1) {
				removeAllLayerDemand(subNetPlan);
				sign = false;
				linkMappingReturn.setSign(sign);
				return linkMappingReturn;
			}
			int kindex = mfsiList.indexOf(kmin);
			selectedPath = candidatePathList.get(kindex);
			//铺设前整体的链路状态
			int [] pathStatusBefore = new int[numberofallslot];
			double pathLength = 0.0;
			for(Link link:selectedPath) {
				pathLength+=link.getLengthInKm();
			}
			String startNodeIndex = String.valueOf(subNodes.indexOf(startNode));
			String endNodeIndex = String.valueOf(subNodes.indexOf(endNode));
			for(Link link:requestLinks) {
				if(link.getOriginNode().getAttribute("MappedNode").equals(startNodeIndex)&&link.getDestinationNode().getAttribute("MappedNode").equals(endNodeIndex)) {
					link.setAttribute("pathlength", String.valueOf(pathLength));
					break;
				}
			}
			double modLevel = 0.0;
			int key = (int)(Math.floor(pathLength/QAM_16maxlength));
			switch(key) {
				case 1: modLevel = 4.0; break;
				case 2: modLevel = 3.0; break;
				case 3: modLevel = 2.0; break;
				case 4: modLevel = 2.0; break;
				default : modLevel = 1.0; break;
			}
			int numberofslotneeded = (int)Math.ceil(capacity/(12.5*modLevel));
			//System.out.println("numberofslotneeded "+numberofslotneeded);
			for(Link link:selectedPath) {
				String s = link.getAttribute("linkstatus");
				int[] s1 = tool.stringToIntArray(s);
				for(int m =0;m<numberofallslot;m++) {
					if(pathStatusBefore[m]==0&&s1[m]==0) {
						pathStatusBefore[m]=0;
					}
					else {
						pathStatusBefore[m]=1;
					}	
				}
			}
			int startindex = 0;
			int endindex = 0;
			int flag=0;
			for(int m=0;m<numberofallslot;m++) {
				if(pathStatusBefore[m]==0) {
					flag++;
				}
				else {
					flag=0;
				}
				if(flag==numberofslotneeded) {
					endindex = m;
					startindex = endindex-numberofslotneeded+1;
					break;
				}
			}
			for(Link link:selectedPath) {
				String s = link.getAttribute("linkstatus");
				int[] s1 = tool.stringToIntArray(s);
				for(int i =startindex;i<=endindex;i++) {
					s1[i]=1;
				}
				s = tool.intArrayToString(s1);
				link.setAttribute("linkstatus", s);
				//System.out.println("link "+subNodes.indexOf(link.getOriginNode())+"->"+subNodes.indexOf(link.getDestinationNode())+": "+link.getAttribute("linkstatus"));
			}
		}
		//铺设完链路之后，要删掉demand!!!!!!
		removeAllLayerDemand(subNetPlan);
		linkMappingReturn.setSign(sign);
		return linkMappingReturn;
	}
	
	public static int numberofDeployedVNF(NetPlan SubNetPlan) {
		int numberofdeployedvnf=0;
		List<Node> subnodelist = SubNetPlan.getNodes();
		for(Node node:subnodelist) {
			if(node.getAttribute("DataCenter").equals("1")) {
				int num=node.getAttribute("VNF").length()-1;
				numberofdeployedvnf=numberofdeployedvnf+num;
			}
		}	
		return numberofdeployedvnf;
	}
	
	public static int MFSI(NetPlan SubNetPlan) {
		int mfsiindex=0;
		Tool_Util tool = new Tool_Util();
		List<Link> subnetplanlinklist = SubNetPlan.getLinks(SubNetPlan.getNetworkLayerDefault());
		List<Integer> maxindexlist = new ArrayList<Integer>();
		for(Link link:subnetplanlinklist) {
			String s = link.getAttribute("linkstatus");
			int[] s1 = tool.stringToIntArray(s);
			int max = 0;
			for(int i =0;i<numberofallslot;i++) {
				if(s1[i]==1) {
					max=i;
				}
			}
			maxindexlist.add(max);
		}
		mfsiindex = Collections.max(maxindexlist);
		return mfsiindex+1;	
	}
	
	/**
	 * 对存放整数类型的集合求平均值
	 * @param list 存放整数类型对象的集合
	 * @return 平均值
	 */
	public static double getAvgvalue(List<Integer> list) {
		double avgvalue = 0.0;
		double sum = 0.0;
		int num = list.size();
		for(int i : list) {
			sum = (double)i+sum;	
		}
		avgvalue = sum/(num*1.0);
		return avgvalue;
	}
	
	/**
	 * 对存放Double类型对象的集合求平均值
	 * @param list 存放Double类型对象的集合
	 * @return 平均值
	 */
	public static double getDoubleAvgvalue(List<Double> list) {
		double avgvalue = 0.0;
		double sum = 0.0;
		int num = list.size();
		for(double i : list) {
			sum = (double)i+sum;	
		}
		avgvalue = sum/(num*1.0);
		return avgvalue;
	}
}
